package SocialMediaSentiment;

import java.util.Vector;

public class levenstein2 {
	static String routearray[][]; //de array om de route te printen
	static Vector<Integer> route;
	
	public static int levenshteinDistance(String first, String second) {
		String start = first.toLowerCase(); 
		String goal = second.toLowerCase();
		route = new Vector<Integer>(); //de vector om de route te printen
		  
		int instertcost = 1 , deletecost = 1; //de costs om de inserten en te deleten
		int startlength = start.length()+1; //de lengte van het startwoord
		int goallength = goal.length()+1; //de lengte van het goalwoord
		int comparearray[][] = new int [startlength][goallength]; //de array moet startlength X goallength zijn
		comparearray[startlength-1][0] = 0; //het element linksonder wordt op 0 gesteld
		routearray = new String[startlength][goallength]; //de route moet ook startlength X goallength zijn
		for( int row = 0; row < startlength; row++)
		{
			for(int column = 0; column <goallength; column++)
			{ 
				routearray[ row ][ column ] = " "; //de routearray wordt op spaties gezet
			}
		}
		routearray[0][goallength-1]= "x"; //met reachtsbovenin een x
		String[] arraystart = start.split("|");   //split een string tot een array
		for (int left=0,  right=arraystart.length-1; left<right; left++, right--) { //om een array om te draaien
			String temp = arraystart[left]; //alle linker elementen
			arraystart[left]  = arraystart[right];//worden vervangen door het rechterelement
			arraystart[right] = temp; //en de rechter door de linker
		}  
		String[] arraygoal = goal.split("|"); //split een string tot een array
		for(int column = 1; column <goallength; column++)
		{
			comparearray[startlength-1][column]= comparearray[startlength-1][column-1]+1;//de onderste row zijn allemaal met costs +1
		}
		for( int row = startlength-2; row >= 0; row--)
		{  
			comparearray[row][0]= comparearray[row+1][0]+1; //de eerste colomn zijn allemaal met costs +1
		}
		for( int column = 1; column <goallength; column++ )
		{
			for( int row = startlength-2; row >= 0; row-- )
			{  
				String a = arraystart[row]; 
				String b = arraygoal[column];
				int x1 = comparearray[row][column-1] + instertcost; //inserten(naar rechts) kost de insertkost
				int x2 = comparearray[row+1][column] + deletecost; //deleten (naar boven) kost de deletekost
				int x3 = comparearray[row+1][column-1] + subcost( a,b ); //vervangen kost 0 of 2
				int min1 =Math.min(x1,x2); //de minimum van 2
				int minus = Math.min(min1, x3); //de minimum van 3
				comparearray[row][column]= minus; //de afstand is de minste
			}
		}
		
		
		int a= 0;
		int b = goallength-1;
		route.add(comparearray[a][b]);
		while ( a < startlength-1 & b >= 0 ){//zolang we niet bij de goal zijn blijf zoeken

			int[] x1 = shortest( a, b, comparearray, startlength-1, goallength-1 ); //vind de beste route vanaf een punt
			a=x1[0]; 
			b =x1[1];//en gooi deze weer in de while
		}
		 return route.firstElement();
		
	}
	private static int subcost ( String a, String b ){
		int cost = 0;
		if(a.equals(b)){ //als de letter gelijk is wordt er niks vervangen
			cost = 0;   // en is de cost dus 0
		}
		else 
			cost = 3; //anders is de cost 2
		return cost;
	}
	private static int[] shortest ( int a, int b, int[][] array, int startlength,int goallength ){
		int newa = 0, newb=0;
		if (a < startlength && b > 0){//als we nog niet bij de rand zijn
			int x1 =array[a+1][b];
			int x2= array[a][b-1];
			int x3 = array[a+1][b-1];
			int min1 =Math.min(x1,x2);
			int minus = Math.min(min1, x3);
			if (minus == x3&& x3 ==x2 &&x2 ==x1) // als alle routes even laag zijn gaan we substitueren we
			{ 
				newa = a+1;
				newb = b-1;
				
			}
			else{
				if (minus == x1) //als naar beneden gaan het laagst is deleten we
				{ 
					newa = a+1;
					newb = b;
					
				}
				if (minus == x2) //als naar links het laagst is inserten we
				{ 
					newa = a;
					newb = b-1;
					
				}
				if (minus == x3) //als schuin het laagst is substitueren we
				{ 
					newa = a+1;
					newb = b-1;
					 
				}
			}
		}
		else if (a >= startlength && b > 0){ //als we onderaan zijn kunnen we alleen nog maar inserten
			newa = a;
			newb = b-1;
			
		}
		else if (a < startlength && b <=0){ //als we links zijn kunnen we alleen nog maar deleten
			newa = a+1;
			newb = b;
			
		}
		routearray[newa][newb] = "x"; //het pad wordt in de routearray gestopt
		route.add(array[newa][newb]); //en aan de route toegevoegd
		int AandB[] ={ newa, newb};
		return AandB;
	}
}